# -*- coding=utf-8 -*-

# 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
# &
# &       I    
# &   I~~~II~I 
# & I~II~IIIIII
# &&&&&&&&&&&&&&&&&&&
# 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图

# 示例:
# 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
# 输出: 6

# 思路：
# 从2头向中间遍历，当出现以下情况
#           I      
#        I  I     I
# I      I  I     I
# I      I  I     I
# 计算当前能盛下的最多的水，短的一方向中心移动一步，并且把整个容器削下去一层
#           I      
#        I  I     I
# 这样继续不停削容器，直到把容器削没有
# 获得的体积即是 容器的墙壁 + 水的容量
# 也就求取出 水的容量了
class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        already_height = 0;
        index_begin = 0;
        index_end = len(height) - 1;
        area = 0;
        while index_begin <= index_end:
            h = min(height[index_begin], height[index_end]);
            w = index_end - index_begin + 1;

            if height[index_begin] < height[index_end]:
                index_begin += 1;
            else:
                index_end -= 1;

            if h == 0 or h < already_height:
                continue;

            area += h * w - already_height * w;

            # print "*" * 15;
            # print "index:";
            # print [index_begin, index_end];
            # print "hw:";
            # print [h, w];
            # print "already_height:";
            # print already_height;
            # print "area:";
            # print area;
            # print "*" * 15;
            # print "\n";

            already_height = h;
        return area - sum(height);


t = Solution();
print t.trap([0,1,0,3,1,0,1,3,2,1,2,1])